package fun.ipconfig.rb;

import fun.ipconfig.DataCompare;

/**
 * @author GZSA
 */
public class RbTreeNode<T extends DataCompare> {
    RbTreeNode<T> parent;
    RbTreeNode<T> left;
    RbTreeNode<T> right;
    RbTreeColor color;
    // 数据
    T data;

    public RbTreeNode(T data) {
        this.data = data;
        // 默认红色
        color = RbTreeColor.red;
    }

    public RbTreeNode<T> getParent() {
        return parent;
    }

    public void setParent(RbTreeNode<T> parent) {
        this.parent = parent;
    }

    public RbTreeNode<T> getLeft() {
        return left;
    }

    public void setLeft(RbTreeNode<T> left) {
        this.left = left;
    }

    public RbTreeNode<T> getRight() {
        return right;
    }

    public void setRight(RbTreeNode<T> right) {
        this.right = right;
    }

    public boolean isBlock() {
        return color.equals(RbTreeColor.block);
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public boolean leftIsNull() {
        return left == null;
    }

    public boolean parentNotNull() {
        return !(parent == null);
    }

    public boolean rightIsNull() {
        return right == null;
    }

    /**
     * 节点比较
     */
    RbTreeIndexStatus getNext(RbTreeNode<T> node) {
        return data.index() == node.data.index() ? RbTreeIndexStatus.EQ :
                (data.index() > node.data.index() ? RbTreeIndexStatus.GT : RbTreeIndexStatus.LT);
    }

    /**
     * 平衡或变色
     *
     * @return
     */
    public boolean reset(RbTree<T> tree) { 
        if (parent.getBrother() == null || !parent.color.equals(parent.getBrother().color)) {
            /** 叔节点不存在 */
            switch (getStatus()) {
                case LR: {
                    leftRight(tree);
                    break;
                }
                case LL: {
                    leftLeft(tree);
                    break;
                }
                case RL: {
                    rightLeft(tree);
                    break;
                }
                case RR: {
                    rightRight(tree);
                    break;
                }
            }
            return true;
        } else {
            /** 颜色相同，往上变色 */
            parent.color = RbTreeColor.block;
            parent.getBrother().color = RbTreeColor.block;
            if (parent.parent != null) {
                if (parent.parent.parent == null) {
                    return true;
                }
                parent.parent.color = RbTreeColor.red;
            }
            return false;
        }
    }

    /**
     * 获取可调整状态
     *
     * @return
     */
    public RbTreeIndexStatus getStatus() {
        if (parent.left == this) {
            return parent.parent.left == parent ? RbTreeIndexStatus.LL : RbTreeIndexStatus.RL;
        } else {
            return parent.parent.left == parent ? RbTreeIndexStatus.LR : RbTreeIndexStatus.RR;
        }
    }

    /**
     * 获取兄弟节点
     *
     * @return
     */
    public RbTreeNode<T> getBrother() {
        return parentNotNull() ? parent.left == this ? parent.right : parent.left : null;
    }

    /**
     * 旋转判断时已经能够确认， pp的右侧必须为空或黑色，p节点必须为红色，且在p节点的左侧插入一个节点(默认插入节点红色)
     * r 表示红色， b 表示黑色 ， 插入时默认红色
     * 插入r1              变色             旋转
     * b3(pp)            r3(pp)         b2(p)
     * /                 /               /  \
     * r2(p)              b2(p)          r1    r3(pp)
     * /                  /
     * r1                 r1
     *
     * @param tree
     */
    private void leftLeft(RbTree<T> tree) {
        RbTreeNode<T> p = parent;
        RbTreeNode<T> pp = parent.parent;
        resetLlOrRrParent(tree);
        pp.setLeft(p.right);
        if (!p.rightIsNull()) {
            p.right.setParent(pp);
        }
        pp.setParent(p);
        p.setRight(pp);
    }

    /**
     * 旋转判断时已经能够确认， pp的左侧必须为空或黑色，p节点必须为红色，且在p节点的右侧插入一个节点(默认插入节点红色)
     * r 表示红色， b 表示黑色 ， 插入时默认红色
     * 插入r3              rr变色            旋转
     * b1(pp)              r1(pp)          b2(p)
     * \                   \            /    \
     * r2(p)               b2(p)    r1(pp)   r3
     * \                   \
     * r3                  r3
     *
     * @param tree
     */
    private void rightRight(RbTree<T> tree) {
        RbTreeNode<T> p = parent;
        RbTreeNode<T> pp = parent.parent;
        resetLlOrRrParent(tree);
        pp.setRight(p.left);
        if (!p.leftIsNull()) {
            p.left.setParent(pp);
        }
        pp.setParent(p);
        p.setLeft(pp);
    }

    /**
     * ll,lr 旋转设置根节
     *
     * @param tree
     */
    private void resetLlOrRrParent(RbTree<T> tree) {
        RbTreeNode<T> p = parent;
        RbTreeNode<T> pp = parent.parent;
        /** 变色 */
        p.color = RbTreeColor.block;
        pp.color = RbTreeColor.red;
        if (pp.equals(tree.root)) {
            tree.root = p;
            p.parent = null;
        } else {
            if (pp.parent.left.equals(pp)) {
                pp.parent.setLeft(p);
            } else {
                pp.parent.setRight(p);
            }
            p.setParent(pp.parent);
        }
    }

    /**
     * 旋转判断时已经能够确认， pp的右侧必须为空或黑色，p节点必须为红色，且在p节点的右侧插入一个节点(默认插入节点红色)
     * 插入节点r2        lr变色
     * b3(pp)          r3(pp)          b2
     * /              /              /   \
     * r1(p)         r1(p)         r1(p)   r3(pp)
     * \               \
     * r2             b2
     *
     * @param tree
     */
    private void leftRight(RbTree<T> tree) {
        RbTreeNode<T> p = parent;
        RbTreeNode<T> pp = parent.parent;
        /**p节点和pp节点的子节点重置*/
        p.setRight(left);
        if (!leftIsNull()) {
            left.setParent(p);
        }
        pp.setLeft(right);
        if (!rightIsNull()) {
            right.setParent(pp);
        }
        resetRlOrLrParent(tree);
        setLeft(p);
        p.setParent(this);
        setRight(pp);
        pp.setParent(this);
    }

    /**
     * 旋转判断时已经能够确认， pp的右侧必须为空或黑色，p节点必须为红色，且在p节点的右侧插入一个节点(默认插入节点红色)
     * 插入节点r2        lr变色               旋转
     * b1(pp)          r1(pp)              b2
     * \               \            /   \
     * r3(p)           r3(p)    r1(p)   r3(pp)
     * /              /
     * r2              b2
     *
     * @param tree
     */
    private void rightLeft(RbTree<T> tree) {
        RbTreeNode<T> p = parent;
        RbTreeNode<T> pp = parent.parent;
        /**p节点和pp节点的子节点重置*/
        pp.setRight(left);
        if (!rightIsNull()) {
            left.setParent(pp);
        }
        p.setLeft(right);
        if (!leftIsNull()) {
            right.setParent(p);
        }
        resetRlOrLrParent(tree);
        setLeft(pp);
        pp.setParent(this);
        setRight(p);
        p.setParent(this);
    }

    /**
     * lr,rl 旋转设置根节
     *
     * @param tree
     */
    public void resetRlOrLrParent(RbTree<T> tree) {
        RbTreeNode<T> p = parent;
        RbTreeNode<T> pp = parent.parent;
        color = RbTreeColor.block;
        pp.color = RbTreeColor.red;
        /** lr,rl 重置 */
        if (pp.equals(tree.root)) {
            tree.root = this;
            this.parent = null;
        } else {
            if (pp.parent.left.equals(pp)) {
                pp.parent.setLeft(this);
            } else {
                pp.parent.setRight(this);
            }
            setParent(pp.parent);
        }
    }

    @Override
    public String toString() {
        StringBuffer buff = new StringBuffer();
        RbTreeNode next = this;
        while (true) {
            if (next.parent != null) {
                buff.append("\t");
                next = next.parent;
            } else {
                break;
            }
        }

        return "{" +
                "\n" + buff + "\t\"data\": " + data +
                (left != null ? (",\n" + buff + "\t\"left " + (left.color) + "\": " + (left == null ? ("\"" + null + "\"") : left)) : "") +
                (right != null ? (",\n" + buff + "\t\"right " + (right.color) + "\": " + (right)) : "") +
                "\n" + buff + "\t}";
    }
}
